package suanfa.paixu;

import java.util.Arrays;
//归并排序
public class Guibin {
    //5,43,34,25
    public static void guibinsort(int[] a,int[] t,int low,int high){
        if(low<high){
            int mid=(low+high)/2;
            guibinsort(a,t,low,mid);//对左边分割
            guibinsort(a,t,mid+1,high);//对右边分割
            //合并
            hebin(a,t,low,mid,high);
        }
    }
    public static void hebin(int[] a,int[] t,int low,int mid,int high){
        int i=low;
        int j=mid+1;
        int k=0;
        while(i<=mid&&j<=high){//将拆开的数组进行比较并赋值
            if(a[i]>a[j]){//这里仅是i或者j+1;在后面可以把没赋值的赋值进去
                t[k++]=a[j++];
            }else{
                t[k++]=a[i++];
            }
        }
        while(i<=mid){
            t[k++]=a[i++];

        }
        while(j<=high){
            t[k++]=a[j++];
        }
        //把t数组的值放回原数组
        k=0;
        while(low<=high){
            a[low++]=t[k++];
        }
    }

    public static void main(String[] args) {
        int[] a={5,43,34,25};
        int[] b=new int[a.length];
        guibinsort(a,b,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }
}
